import copy

class Solution(object):
    def wiggleSort(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        tmp = copy.copy(nums)
        tmp.sort()
        n = (len(nums)+1)//2
        first = tmp[:n]
        second = tmp[n:]
        pairs = []
        if len(first)==len(second):
            for i in range(n):
                pairs.append((first[i], second[i]))
            pairs.sort(key=lambda pair:pair[0],reverse=True)
            for i, pair in enumerate(pairs):
                nums[i*2]=pair[0]
                nums[i*2+1]=pair[1]
        else:
            for i in range(n-1):
                pairs.append((first[i+1], second[i]))
            pairs.sort(key=lambda pair:pair[0],reverse=True)            
            for i, pair in enumerate(pairs):
                nums[i*2]=pair[0]
                nums[i*2+1]=pair[1]
            nums[-1]=first[0]
